package leetcode_100;

/**
 *@author 周杨
 *SetMatrixZeroes_73 给定一个M*N的矩阵 如果发现某位是0 则把该行该列的所有数字置0
 *describe: 用一个矩阵中不会出现的数字坐标记位 第一次扫描把所有要置0的数标记 时间复杂度O(m+n) 空间复杂度O(1) AC 27%
 *2018年5月12日 下午9:53:27
 */
public class SetMatrixZeroes_73 {

	public static void main(String[] args) {
		SetMatrixZeroes_73 test=new SetMatrixZeroes_73();
		int matrix[][]=new int[][] {{1,1,0},{1,0,1},{1,1,1}};
		test.setZeroes(matrix);
		test.print(matrix);
	}
	
	public void print(int [][] matrix) {
		for(int i=0;i<matrix.length;++i) {
			for(int j=0;j<matrix[0].length;++j) {
				System.out.print(matrix[i][j]+" ");
			}
			System.out.println();
		}
				
	}
	
	public void setZeroes(int[][] matrix) {
		 if (matrix==null || matrix.length==0) {
	            return;
	        }
	        
	        int m = matrix.length;
	        int n = matrix[0].length;
	        final int indicator = -167364526;
	        
	        for (int i=0; i<m; i++) {
	            for (int j=0; j<n; j++) {
	                if (matrix[i][j] == 0) {
	                    for (int x=0; x<m; x++) {
	                        if (x==i || matrix[x][j]==0|| matrix[x][j]==indicator) {
	                            continue;
	                        }
	                        matrix[x][j] = indicator;
	                    }
	                    for (int y=0; y<n; y++) {
	                        if (y==j || matrix[i][y]==0|| matrix[i][y]==indicator) {
	                            continue;
	                        }
	                        matrix[i][y] = indicator;
	                    }
	                }
	            }
	        }
	        for (int i=0; i<m; i++) {
	            for (int j=0; j<n; j++) {
	                if (matrix[i][j] == indicator) {
	                    matrix[i][j] = 0;
	                }
	            }
	        }
    }
}
